package sort;
import java.util.PriorityQueue;
public class DuiSort {
    public int[] sortArray(int[] nums) {
    int len = nums.length;
    //先调整一遍，整理成堆
    heapify(nums);
    //循环保证,[0, i]堆有序
        for (int i = len - 1; i >= 1; ) {
        //将堆顶元素换到末尾
        swap(nums, 0, i);
        //下次待排序区间为[0, i - 1]，逐步减少堆有序的部分
        i --;
        //调整刚加入到堆顶的元素，让堆整体满足最大堆性质
        siftDown(nums, 0, i);
    }
        return nums;
}
    public void heapify(int []nums) {
        int len = nums.length;
        //从第一个非叶子结点位置(len - 1 / 2)开始调整，每次调整的范围是[i, len - 1]
        for (int i = (len - 1) / 2; i >= 0; i -- ) {
            siftDown(nums, i, len - 1);
        }
    }
    public void siftDown(int []nums, int k, int end) {
        //k为当前位置，end为最大的范围
        //先判断左儿子是否在范围内
        while (2 * k + 1 <= end) {
            //由于要变化，所以先存储左儿子
            int j = 2 * k + 1;
            //判断右儿子是否在单位内，先左右孩子比较找出较大的
            if (j + 1 <= end && nums[j + 1] > nums[j]) {
                j ++;
            }
            //如果比父节点大，就交换，否则退出
            if (nums[j] > nums[k]) {
                swap(nums, j, k);
            } else {
                break;
            }
            //迭代往下，让当前结点变成儿子结点
            k = j;
        }
    }
    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public  int[] findKnum(int[] nums,int k){
        if (nums.length==0){
            return  nums;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int a: nums) {
            if (queue.size()<k){
                queue.add(a);
            }else {
                queue.poll();
                queue.add(a);
            }
        }
        int[]  res= new int[queue.size()];
        int i=0;
        while (!queue.isEmpty()){
            res[i++]= queue.poll();
        }
        return  res;
    }
    public static void main(String[] args) {
        DuiSort duiSort = new DuiSort();
        int[] ints = duiSort.findKnum(new int[]{2, 3, 5, 1},2);
        for (int a:ints
             ) {
            System.out.println(a);
        }
    }
}
